package A_review.review9_4;

public class QuickSortt {


     int[] quickSort(int[] nums){
         if (nums.length==0){
             return nums;
         }
         sort(nums,0,nums.length-1);
         return  nums;
     }

     void  sort(int[]  nums,int lo,int hi){
         //TODO:2023/9/4 递归一定要 写递归终止条件
         if (lo>hi){
             return;
         }
         int partition = partition(nums, lo, hi);
         sort(nums,lo,partition-1);
         sort(nums,partition+1,hi);
     }


     int  partition(int[] nums,int lo,int hi){
         int part=nums[lo];
         int j=lo+1;
         int k=hi;

         while (j<=k){
              while (nums[j]<=part&&j<=hi){
                  j++;
              }
              while (nums[k]>part&&k>=lo){
                  k--;
              }
              if (j>k){
                  break;
              }
              swap(nums,j,k);
         }
         swap(nums,lo,k);

         return  k;

     }


     void  swap(int[] nums,int j,int k){
         int temp=nums[j];
         nums[j]=nums[k];
         nums[k]=temp;
     }

    public static void main(String[] args) {
        QuickSortt quickSortt = new QuickSortt();
        int[] arr={2,3,1,4,6,4,7,12};
        int[] ints = quickSortt.quickSort(arr);
        for (int a:ints
             ) {
            System.out.println(a);

        }

    }




}
